// https://leetcode.cn/problems/perfect-squares/description/

// 算法思路总结：
// 1. 动态规划解决完全平方数问题（完全背包最小值）
// 2. 状态定义：dp[j]表示凑出整数j所需的最少完全平方数个数
// 3. 物品集合：1², 2², ..., (√n)² 这些完全平方数
// 4. 状态转移：dp[j] = min(dp[j], dp[j-i²] + 1)
// 5. 正序遍历允许数字重复使用（完全背包）
// 6. 时间复杂度：O(n√n)，空间复杂度：O(n)

#include <iostream>
using namespace std;

#include <cmath>
#include <vector>
#include <algorithm>

class Solution 
{
public:
    const int INF = 0x3f3f3f3f;
    int numSquares(int n) 
    {
        int m = sqrt(n);
        vector<int> dp(n + 1, INF);
        dp[0] = 0;

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 0 ; j <= n ; j++)
            {
                if (j - i * i >= 0)
                {
                    dp[j] = min(dp[j], dp[j - i * i] + 1);
                }
            }
        }
        
        return dp[n];
    }
};

int main()
{
    int n1 = 12, n2 = 13;
    Solution sol;

    cout << sol.numSquares(n1) << endl;
    cout << sol.numSquares(n2) << endl;

    return 0;
}